package pfq.demo.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序
 * 思路：采用分治思想，将一个大问题拆分为很多小问题，然后分而治之，小问题解决了，大问题也就解决了
 * 具体是把待排序的数组一分为二，各自排序，排好序后，再将两者合并成一个数组
 */
public class MergeSort {

    public static void main(String[] args) {

        int[] data = Arrays.copyOf(Utils.data(), Utils.data().length);
        System.out.println("排序前：" + Arrays.toString(data));
        mergeSort(data);
        System.out.println("排序后：" + Arrays.toString(data));

    }

    public static void mergeSort(int[] a) {
        if (a == null || a.length == 1) {
            return;
        }

        mergeSort_(a, 0, a.length - 1);
    }

    public static void mergeSort_(int[] a, int p, int r) {

        if (p >= r) {
            return;
        }

        // 求p~r之间的中间元素下标，不是(p+r)/2
        int q = p + (r - p) / 2;

        mergeSort_(a, p, q);
        mergeSort_(a, q + 1, r);

        merge(a, p, q, r);

    }

    public static void merge(int[] a, int p, int q, int r) {
        // 创建一个与两区间大小一样的临时数组
        int[] tempA = new int[r - p + 1];

        int i = p;
        int j = q + 1;// 此处是q+1才能指向右边数组的第一个元素
        int k = 0;

        while (i <= q && j <= r) {

            if (a[i] <= a[j]) {
                tempA[k++] = a[i++];
            } else {
                tempA[k++] = a[j++];
            }

        }

        // TODO 此处可以利用哨兵简化掉
        // 说明左边数组还有数据
        if (i <= q) {
            while (i <= q) {
                tempA[k++] = a[i++];
            }

            // 说明右边数组还有数据
        } else if (j <= r) {
            while (j <= r) {
                tempA[k++] = a[j++];
            }
        }


        // 将临时数组拷贝到原数组中
        for (i = 0; i < tempA.length; i++) {
            a[p + i] = tempA[i];
        }


    }

}
